lang/C/sorting.and.searching.cormen.algo/Introduction to Algorithms, Third Edition/code/bin.c

   1 /* binary search tree */
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5
   6 #define compLT(a,b) (a < b)
   7 #define compEQ(a,b) (a == b)
   8
   9 /* implementation dependent declarations */
  10 typedef enum {
  11     STATUS_OK,
  12     STATUS_MEM_EXHAUSTED,
  13     STATUS_DUPLICATE_KEY,
  14     STATUS_KEY_NOT_FOUND
  15 } statusEnum;
  16
  17 typedef int keyType;            /* type of key */
  18
  19 /* user data stored in tree */
  20 typedef struct {
  21     int stuff;                  /* optional related data */
  22 } recType;
  23
  24 typedef struct nodeTag {
  25     struct nodeTag *left;       /* left child */
  26     struct nodeTag *right;      /* right child */
  27     struct nodeTag *parent;     /* parent */
  28     keyType key;                /* key used for searching */
  29     recType rec;                /* user data */
  30 } nodeType;
  31
  32 nodeType *root = NULL;          /* root of binary tree */
  33
  34 statusEnum insert(keyType key, recType *rec) {
  35     nodeType *x, *current, *parent;
  36
  37    /***********************************************
  38     *  allocate node for data and insert in tree  *
  39     ***********************************************/
  40
  41     /* find future parent */
  42     current = root;
  43     parent = 0;
  44     while (current) {
  45         if (compEQ(key, current->key))
  46             return STATUS_DUPLICATE_KEY;
  47         parent = current;
  48         current = compLT(key, current->key) ?
  49             current->left : current->right;
  50     }
  51
  52     /* setup new node */
  53     if ((x = malloc (sizeof(*x))) == 0) {
  54         return STATUS_MEM_EXHAUSTED;
  55     }
  56     x->parent = parent;
  57     x->left = NULL;
  58     x->right = NULL;
  59     x->key = key;
  60     x->rec = *rec;
  61
  62     /* insert x in tree */
  63     if(parent)
  64         if(compLT(x->key, parent->key))
  65             parent->left = x;
  66         else
  67             parent->right = x;
  68     else
  69         root = x;
  70
  71     return STATUS_OK;
  72 }
  73
  74 statusEnum delete(keyType key) {
  75     nodeType *x, *y, *z;
  76
  77    /***************************
  78     *  delete node from tree  *
  79     ***************************/
  80
  81     /* find node in tree */
  82     z = root;
  83     while(z != NULL) {
  84         if(compEQ(key, z->key))
  85             break;
  86         else
  87             z = compLT(key, z->key) ? z->left : z->right;
  88     }
  89     if (!z) return STATUS_KEY_NOT_FOUND;
  90
  91     /* find tree successor */
  92     if (z->left == NULL || z->right == NULL)
  93         y = z;
  94     else {
  95         y = z->right;
  96         while (y->left != NULL) y = y->left;
  97     }
  98
  99     /* point x to a valid child of y, if it has one */
 100     if (y->left != NULL)
 101         x = y->left;
 102     else
 103         x = y->right;
 104
 105     /* remove y from the parent chain */
 106     if (x) x->parent = y->parent;
 107     if (y->parent)
 108         if (y == y->parent->left)
 109             y->parent->left = x;
 110         else
 111             y->parent->right = x;
 112     else
 113         root = x;
 114
 115     /* if z and y are not the same, copy y to z. */
 116     if (y != z) {
 117         z->key = y->key;
 118         z->rec = y->rec;
 119     }
 120
 121     free (y);
 122     return STATUS_OK;
 123 }
 124
 125 statusEnum find(keyType key, recType *rec) {
 126
 127    /*******************************
 128     *  find node containing data  *
 129     *******************************/
 130
 131     nodeType *current = root;
 132     while(current != NULL) {
 133         if(compEQ(key, current->key)) {
 134             *rec = current->rec;
 135             return STATUS_OK;
 136         } else {
 137             current = compLT(key, current->key) ?
 138                 current->left : current->right;
 139         }
 140     }
 141     return STATUS_KEY_NOT_FOUND;
 142 }
 143
 144 int main(int argc, char **argv) {
 145     int i, maxnum, random;
 146     recType *rec;
 147     keyType *key;
 148     statusEnum status;
 149
 150     /* command-line:
 151      *
 152      *   bin maxnum random
 153      *
 154      *   bin 5000        // 5000 sequential
 155      *   bin 2000 r      // 2000 random
 156      *
 157      */
 158     maxnum = atoi(argv[1]);
 159     random = argc > 2;
 160
 161     if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
 162         fprintf (stderr, "insufficient memory (rec)\n");
 163         exit(1);
 164     }
 165     if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
 166         fprintf (stderr, "insufficient memory (key)\n");
 167         exit(1);
 168     }
 169
 170     if (random) { /* random */
 171         /* fill "key" with unique random numbers */
 172         for (i = 0; i < maxnum; i++) key[i] = rand();
 173         printf ("ran bt, %d items\n", maxnum);
 174     } else {
 175         for (i=0; i<maxnum; i++) key[i] = i;
 176         printf ("seq bt, %d items\n", maxnum);
 177     }
 178
 179
 180     for (i = 0; i < maxnum; i++) {
 181         status = insert(key[i], &rec[i]);
 182         if (status) printf("pt1, i=%d: %d\n", i, status);
 183     }
 184
 185     for (i = maxnum-1; i >= 0; i--) {
 186         status = find(key[i], &rec[i]);
 187         if (status) printf("pt2, i=%d: %d\n", i, status);
 188     }
 189
 190     for (i = maxnum-1; i >= 0; i--) {
 191         status = delete(key[i]);
 192         if (status) printf("pt3, i=%d: %d\n", i, status);
 193     }
 194     return 0;
 195 }